
public class Sort {
	
	public int[] merge(int[]a)
	{
		int[] sorted = new int[a.length];
		if(a.length == 1){
			return a;
		}else if(a.length == 2)
		{  
			int[] temp = new int[2];
			if(a[0] > a[1])
			{
				temp[0] = a[1];
				temp[1] = a[0];
			}else
			{
				temp[0] = a[0];
				temp[1] = a[1];
			}
			return temp;
			
		}else{
			//int[] a1 = new int[a.length/2];
			//int[] a2 = new int[a.length -(a.length/2)];

			//System.arraycopy(src, 1, dst, 0, 3); // Copies 2, 3, 4 into dst
			int[] a1 = java.util.Arrays.copyOfRange(a, 0, a.length/2);
			int[] a2 = java.util.Arrays.copyOfRange(a, a.length/2 , a.length);
			int[] b1 = new int[a1.length];
			int[] b2 = new int[a2.length];
			b1 = merge(a1);
			b2 = merge(a2);
			sorted = combine(b1,b2);
			
			return sorted;
			
		}
		
	}

	private int[] combine(int[] a1, int[] a2) {
		
		int j = 0;
		int k = 0;
		int[] comb = new int[a1.length + a2.length];
	
		for(int i = 0; i < (a1.length + a2.length); i++)
		{
			if(j == a1.length)
			{
				j--;
				//Place infinity (could have used a sentinel value)
				a1[j] = 1999999999;
			}
			if(k == a2.length)
			{
				k--;
				//Place infinity (could have used sentinel value)
				a2[k] = 1999999999;
			}
			if(a1[j] < a2[k])
			{
				comb[i] = a1[j];
				j++;
			}else
			{
				comb[i] = a2[k];
				k++;
			}
		}
		// TODO Auto-generated method stub
		return comb;
	}
	
	public int[] bubble(int[]a)
	{
	    int[] sorted = a;
	    for(int i=0; i < sorted.length; i++)
	    {
	    	for(int j = 0; j< sorted.length-1; j++)
	    	{
	    		//Swap if smaller
	    		if(sorted[j+1]<sorted[j])
	    		{
	    			int temp = sorted[j];
	    			a[j] = a[j+1];
	    			a[j+1] = temp; 
	    		}
	    	}
	    		
	    }
		
		return sorted;
	}
	
	public int[] selection(int[]a)
	{
		int[]sorted = a;
		for(int i = 0; i< a.length-1; i++)
		{
			int min = i;
			for(int j= i+1; j<a.length;j++ )
			{
				if(sorted[min]> sorted[j]){
					min = j;
				}
			}
			//Swap
			int temp = sorted[i];
			sorted[i] = sorted[min];
			sorted[min]= temp;
		}
		
		
		return sorted;
	}
	public static void main(String[] args)
	{
		Sort mysort = new Sort();
		int[]arr = new int[]{2,56, 43, 12, 1, 17, 23, 36, 4, 77, 88, 2, 31, 48, 65};
		//int[]arr = new int[]{2,56, 43, 12, 1};
		int[] mergearr = mysort.merge(arr);
		int[] bubblarr = mysort.bubble(arr);
		int[] selectarr = mysort.selection(arr);
		System.out.println("Using merge sort:");
		for(int num : mergearr)
		{
			System.out.print(num + " ");
		}
		
		System.out.println("\nUsing bubble sort:");
		for(int num : bubblarr)
		{
			System.out.print(num + " ");
		}
		

		System.out.println("\nUsing Selection sort:");
		for(int num : selectarr)
		{
			System.out.print(num + " ");
		}
	}

}
